package com.example.leetcode.solution;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution20 {
    public static boolean isValid(String s) {

        Map<Character,Character> charMap = new HashMap(){{
            put(')','(');
            put(']','[');
            put('}','{');
        }};

        List<Character> l = new ArrayList<>();
        for(int i = 0 ; i < s.length(); i++){
            char c = s.charAt(i);
            if(charMap.get(c) == null){
                l.add(c);
            }else{
                if(l.size() == 0){
                    return false;
                }else{
                    char c2 = l.get(l.size() - 1);
                    char c3 = charMap.get(c);
                    if(c3 != c2){
                        return false;
                    }else{
                        l.remove(l.size() - 1);
                    }
                }
            }
        }
        return l.size() == 0;
    }
}
